:- module(sym_expr). :- export construct_group / 9. :- export value_spec_to_range / 3. :- export generic_from_point / 6. :- export generic_to_point / 5. :- export construct_group / 8. :- comment(summary, "Library for expressing the symmetries of a CSP"). :- comment(desc, html(" This library provides a convenient way to express the symmetries of a\n CSP, as described in:

\n\n Warwick Harvey, Tom Kelsey and Karen Petrie. \"Symmetry Group Expression\n for CSPs.\" In Barbara Smith et al., editors, Proceedings of\n SymCon'03: Third International Workshop on Symmetry in Constraint\n Satisfaction Problems, a workshop of CP 2003, pages 86-96.\n September, 2003.

\n\n This is particularly useful for GAP-based symmetry-breaking libraries, as\n it will construct an appropriate group in GAP and provide predicates for\n mapping between CSP assignments and the points acted on by the GAP group.

\n\n Please note that this library currently does not work on Windows machines\n due to its dependence on the GAP interface library.

\n")). :- comment(see_also, [library(gap)]). :- comment(author, "Warwick Harvey"). :- comment(status, evolving). :- comment(construct_group / 8, [summary : "Constructs a GAP group based on the provided symmetry specification.", args : ["Array" : "The array of search variables", "VarDimNames" : "A list of symbolic names for each dimension in Array", "ValueSpec" : "The symbolic name for values and their range", "SymSpecs" : "A list of symmetry specifiers", "GroupName" : "The GAP name to give the constructed group (string)", "MaxPoints" : "The number of GAP points operated on by group", "ToPointPred" : "A predicate for converting a variable/value assignment to a GAP point", "FromPointPred" : "A predicate for converting a GAP point to a variable/value assignment"], amode : construct_group(+, ++, ++, ++, ++, -, -, -), desc : html(" This predicate is intended for use in conjunction with a\n GAP/ECLiPSe-based symmetry breaking method. Given an array of search\n variables (Array) and a description of the symmetries, this predicate\n constructs the corresponding group in GAP (GroupName) and returns a pair\n of `to point' and `from point' predicates suitable for use in\n conjunction with it.

\n\n In order to facilitate the expression of the symmetries, a list of\n symbolic names (VarDimNames) is required, to specify a symbolic name for\n each of the dimensions of Array. Similarly, some way is needed to\n refer to the value `dimension'; this is provided by ValueSpec, which is\n of the form ValueName:ValueRange. ValueRange specifies the range of\n values the variables may take (this is just used for constructing the\n group; it is not imposed on the variables) and must be of the form\n Lo..Hi.

\n\n The symmetries (SymSpecs) are then specified by a list with entries of\n the form symmetry(Symmetry, SymmetryDimensions, OtherDimensions).\n Roughly speaking, Symmetry specifies the base symmetry,\n SymmetryDimensions specifies which dimensions it applies to, and\n OtherDimensions specifies which other dimensions should be treated\n specially with respect to this symmetry (if any). The options for\n Symmetry are:\n

\n
s_n
\n\t
(1 dimension)
\n\t
Full permutation of the indices of the specified dimension.
\n\n
cycle
\n\t
(1 dimension)
\n\t
Indices may be cycled (i.e. all shifted k positions modulo the\n\tsize of the dimension).
\n\n
r_4
\n\t
(2 dimensions)
\n\t
Rotational symmetry of the square. The two dimensions specified\n\tmust be of equal size.
\n\n
d_4
\n\t
(2 dimensions)
\n\t
Full symmetry of the square (i.e. including reflections). The\n\ttwo dimensions specified must be of equal size.
\n\n
reverse
\n\t
(1 dimension)
\n\t
Indices may be reversed.
\n\n
gap_group(GroupFunc)
\n\t
(no fixed number of dimensions)
\n\t
The symmetries described by the group returned by the GAP\n\tfunction GroupFunc. GroupFunc should accept a single argument,\n\twhich is a list of the sizes of the dimensions that the symmetry is\n\texpected to act upon. The mapping between GAP points and the\n\telements of the subarray that this symmetry acts upon is obtained\n\tby numbering the indices of the elements in lexicographic order\n\t(first dimension most significant). For example, if the symmetry\n\tsubarray is of size MxN, then the element with index [I,J] is\n\tmapped to point (I-1)*N + J, so that [1,1]->1, [1,N]->N, [2,1]->N+1,\n\tetc.
\n\n
function(Func)
\n\t
(no fixed number of dimensions)
\n\t
Allows a generator to be specified via an ECLiPSe function Func,\n\ta la classic SBDS symmetry functions. Func should accept three\n\t(extra) arguments: DimSizes, SrcIdx and DestIdx. The first,\n\tDimSizes, is a list of the sizes of the dimensions that the symmetry\n\tis expected to act upon. The second, SrcIdx, provides the index of\n\tan element of the subarray that the symmetry acts upon. The third,\n\tDestIdx, should then be unified with the index of the element that\n\tSrcIdx is mapped to by this function. For example, if the generator\n\tis intended to exchange the dimensions of a square array (i.e.\n\treflect along the leading diagonal), if `swap_dim' is passed as\n\tFunc, then the definition of `swap_dim' might be\n\t
swap_dim([N, N], [I, J], [J, I]).
\n\t
Note that for 1-dimensional arrays, DestIdx may be returned as\n\tjust an integer rather than a length-1 list containing the integer,\n\tif desired.
\n\n
table(Generator)
\n\t
(no fixed number of dimensions)
\n\t
Allows a generator to be specified via a lookup table.\n\tGenerator must be an array of same size as the subarray the\n\tsymmetry acts upon, with each element containing the index of the\n\telement that that element should be mapped to.
\n\t
Note that for 1-dimensional arrays, an index may be specified\n\tusing just an integer rather than a length-1 list containing the\n\tinteger, if desired.
\n
\n SymmetryDimensions must be a list with one entry for each dimension of\n the base symmetry. Each entry must either be the name of a dimension,\n or of the form Dimension:IdxSpec, where Dimension is the name of a\n dimension and IdxSpec specifies a subset of the indices of that\n dimension. IdxSpec may be an integer, an integer range L..H, or a list\n of these. Providing such a qualification means that the symmetry is\n only applied to the specified indices of the dimension, not the\n dimension as a whole.

\n\n By default, a symmetry affects the array as a whole; that is, for\n example, a symmetry applied to columns will affect all rows, and in\n particular all rows in the same way (it won't, say, swap columns 1 and 3\n in row 1, but swap 5 and 6 in row 2; the columns will be rearranged in\n the same way in every row). If one or more indices for a dimension\n should be affected independently of the rest of the indices for that\n dimension, then this can be specified in the OtherDimensions field,\n which is a list of terms of the form Dimension:IdxSpec. This specifies\n that the symmetry should only affect the given indices of the given\n dimension, independent of the other indices (the specified indices are\n still affected synchronously). This allows one to express, for example,\n that the elements of a given row can be permuted, independent of the\n other rows. If OtherDimensions is just the empty list, then it may be\n omitted.

\n\n

\n
To do:
\n\t
Support multiple value dimensions
\n\t
Support multiple matrices
\n\t
More error checking... :)
\n
\n"), eg : html("
Balanced Incomplete Block Design (BIBD)
\n\t
Standard model, with a 2-D array of booleans.
\n\t
Full row and column permutation.
\n

\n\t

dim(Array, [NRows, NCols]),
\n\t
...
\n\t
construct_group(Array, [rows, cols], values:0..1, [
\n\t\t
symmetry(s_n, [rows], []),
\n\t\t
symmetry(s_n, [cols], [])
\n\t\t
], \"bibd_group\", MaxPoints, ToPointPred, FromPointPred)
\n

\n

Social golfer problem
\n\t
Boolean model, with one boolean variable for each round/group/player\n\tcombination.
\n\t
Full permutation of the rounds, full permutation of the groups in\n\tany round, and full permutation of the players.
\n

\n\t

dim(Array, [NRounds, NGroups, NPlayers]),
\n\t
...
\n\t
construct_group(Array, [rounds, groups, players], values:0..1, [
\n\t\t
symmetry(s_n, [rounds], []),
\n\t\t
symmetry(s_n, [groups], [rounds:1]),
\n\t\t
symmetry(s_n, [players], [])
\n\t\t
], \"golf_group\", MaxPoints, ToPointPred, FromPointPred)
\n

\n\t

Note that the permutation of the groups within a round does not\n\tneed to be specified for every round; the fact that the rounds are\n\tinterchangeable means that it need only be specified for one round.
\n

\n

N Queens problem
\n\t
Standard row model, with one integer for each row specifying which\n\tcolumn the queen appears in.
\n\t
The symmetries of the square, including reflection, applied to the\n\trow/column combination.
\n

\n\t

dim(Array, [NQueens]),
\n\t
...
\n\t
construct_group(Array, [rows], cols:1..NQueens, [
\n\t\t
symmetry(d_4, [rows, cols], [])
\n\t\t
], \"queens_group\", MaxPoints, ToPointPred, FromPointPred)
\n

\n

N Queens problem
\n\t
Boolean model, with one boolean for each location on the board,\n\tspecifying whether a queen appears there or not.
\n\t
The symmetries of the square, including reflection.
\n

\n\t

dim(Array, [NQueens, NQueens]),
\n\t
...
\n\t
construct_group(Array, [rows, cols], values:0..1, [
\n\t\t
symmetry(d_4, [rows, cols], [])
\n\t\t
], \"queens_group\", MaxPoints, ToPointPred, FromPointPred)
\n

\n\t

Note that the symmetry expression for this model is exactly the\n\tsame as for the standard row model; whether the columns are values\n\tor a dimension of the variable array is irrelevant.
\n")]). :- comment(construct_group / 9, hidden).